package cn.xaut.周赛.m227;

/**
 * 5675. 最接近目标值的子序列和
 */
public class demo5675 {

    public int minAbsDifference(int[] nums, int goal) {

        int len = nums.length;
        int n = (int) Math.pow(2, len);
        boolean[][] flag = new boolean[n][len];
        // 初始化数组
        int x = n / 2;
        for (int j = 0; j < len; j++) {
            boolean t = true;
            for (int i = 0; i < n; i++) {
                if (i % x == 0)
                    t = !t;
                flag[i][j] = t;
            }
            x /= 2;
        }

        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < len; j++) {
                if (flag[i][j])
                    sum += nums[j];
            }
            int diff = Math.abs(sum - goal);    // 差
            res = Math.min(res, diff);
        }
        return res;
    }

    public static void main(String[] args) {

        System.out.println(new demo5675().minAbsDifference(new int[]{5, -7, 3, 5}, 6)); // 0
        System.out.println(new demo5675().minAbsDifference(new int[]{7, -9, 15, -2}, -5));  // 1
        System.out.println(new demo5675().minAbsDifference(new int[]{1, 2, 3}, -7));    // 7
//        System.out.println(new demo5675().minAbsDifference(new int[]{3346,-3402,-9729,7432,2475,6852,5960,-7497,3229,6713,8949,9156,3945,-8686,1528,5022,-9791,-3782,-191,-9820,7720,-6067,-83,6793,340,7793,8742,8067}, -20357));
    }
}
